package 九章算法DP;

/**坐标型动态规划
 * 由于业绩优秀，公司给小Q放了n天的假，身为工作狂的小Q打算在假期中工作、锻炼和休息。
 * 他有个奇怪的习惯:不会连续两天工作或者锻炼。只有当公司营业时，小Q才能去工作，只有当、
 * 健身房营业时，小Q才能去健身，小Q一天只能干一件事。给出假期中公司，健身房的营业情况，
 * 求小Q最少需要休息几天
 *
 * 输入描述:
 * 第一行一个整数，表示放假天数。
 * 第二行n个数，每个数为0或1，第i个数表示公司在第i天是否营业
 * 第三行n个数，每个数为0或1，第i个数表示健身房在第i天是否营业
 * (1为营业 0为不营业)
 *
 * 类似于打劫房屋
 */

public class _最短假期 {
    public static void main(String[] args) {
        // 答案:2 第一天工作，第二天或者第三天健身，最少休息2天
        int n = 4;
        int[] company = {1, 1, 0, 0};
        int[] fitness = {0, 1, 1, 0};
        int target = minHoliday(n, company, fitness);
        System.out.println(target);
    }

    public static int minHoliday(int n, int[] company, int[] fitness) {
        // dp[i][j]表示第i天干了j这个事情的最小休息天
        // 0:工作 1:锻炼 2:休息
        int[][] dp = new int[n + 1][3];
        // 求最小，故全部初始化为无穷大
        for (int i = 0 ; i < n + 1 ; i++) {
            for (int j = 0 ; j < 3 ; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        // 从后往前遍历 将额外的一个元素赋值
        dp[n][0] = 0;
        dp[n][1] = 0;
        dp[n][2] = 1;

        // 从第二位开始遍历
        for (int i = n - 1 ; i >= 0 ; i--) {
            // 若公司开门
            if (company[i] == 1) {
                dp[i][0] = Math.min(dp[i + 1][1], dp[i + 1][2]);
            }
            // 若健身房开门
            if (fitness[i] == 1) {
                dp[i][1] = Math.min(dp[i + 1][0], dp[i + 1][2]);
            }
            // 都不开门，只能休息
            dp[i][2] = Math.min(dp[i + 1][0], Math.min(dp[i + 1][1], dp[i + 1][2])) + 1;
        }
        return Math.min(dp[0][0], Math.min(dp[0][1], dp[0][2]));
    }
}
